package random;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Random;

public class RandomWalk {

	public static int SIZE = 256;

	public Stats CalculateLengthASaw(int[] stepSizes) {
		final int localSize = SIZE;
		final Array2d map = new CompactArray2d(localSize);

		final int xInit = localSize / 2;
		final int yInit = localSize / 2;
		int x = xInit;
		int y = yInit;
		map.get(x, y);
		map.set(x, y);

		final java.util.Random r = new Random();
//		MersenneTwisterFast r = new MersenneTwisterFast(r2.nextLong());
		int length = 0;
		int step = 0;
		int stepSize = stepSizes[step % stepSizes.length];
		int lastDir = r.nextInt(4);
		int dirMask = 15;
		/*
		 * while (calculatePossibleDirections(map, x, y, dir, stepSize) != 0) {
		 * // if(step%100 == 1) // System.out.println(step); loop: while (true)
		 * { rand = r.nextInt(3); switch ((lastDir+rand+1)%4) { case 0: if
		 * (dir[0][stepSize - 1]) { for (int i = 0; i < stepSize; i++) {
		 * map.set(--x, y); } break loop; } break; case 1: if (dir[1][stepSize -
		 * 1]) { for (int i = 0; i < stepSize; i++) { map.set(x, --y); } break
		 * loop; } break; case 2: if (dir[2][stepSize - 1]) { for (int i = 0; i
		 * < stepSize; i++) { map.set(++x, y); } break loop; } break; case 3: if
		 * (dir[3][stepSize - 1]) { for (int i = 0; i < stepSize; i++) {
		 * map.set(x, ++y); } break loop; } break; } } lastDir =
		 * (lastDir+rand+3)%4; step++; length += stepSize; stepSize =
		 * stepSizes[step % stepSizes.length]; } /
		 */
		int i = 0;
		int stepDir = 0;
//		WalkRenderer rend = new WalkRenderer(localSize*2, 10);
//		ArrayList<double[]> points = new ArrayList<double[]>();
//		double[] p = {x,y};
//		points.add(p);
//		rend.setWalk(points.toArray(new double[0][0]));
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 4);
				switch (stepDir) {
				case 0:
					for (i = 0; i < stepSize && !map.get(x - i - 1, y); i++);
					if (i == stepSize) {
						for (int j = 0; j < stepSize; j++) {
							map.set(--x, y);
						}
						break loop;
					}
					break;
				case 1:
					for (i = 0; i < stepSize && !map.get(x, y - i - 1); i++);
					if (i == stepSize) {
						for (int j = 0; j < stepSize; j++) {
							map.set(x, --y);
						}
						break loop;
					}
					break;
				case 2:
					for (i = 0; i < stepSize && !map.get(x + i + 1, y); i++);
					if (i == stepSize) {
						for (int j = 0; j < stepSize; j++) {
							map.set(++x, y);
						}
						break loop;
					}
					break;
				case 3:
					for (i = 0; i < stepSize && !map.get(x, y + i + 1); i++);
					if (i == stepSize) {
						for (int j = 0; j < stepSize; j++) {
							map.set(x, ++y);
						}
						break loop;
					}
					break;
				}
				// only when no step was taken
				dirMask &= ~(1 << (stepDir));
			}
			if (dirMask != 0) {
//				double[] pTemp = {x,y};
//				points.add(pTemp);
//				rend.setWalk(points.toArray(new double[0][0]));
				lastDir = (stepDir + 2) % 4;
				dirMask = 15 & ~(1 << lastDir);
				step++;
				length += stepSize;
				stepSize = stepSizes[step % stepSizes.length];
			}
		}
		/**/
		Stats stats = new Stats();
		stats.pathLength = length;
		stats.stepLength = step;
		stats.endLength = Math.sqrt((x - xInit) * (x - xInit) + (y - yInit)
				* (y - yInit));
		stats.manEndLength = Math.abs(x - xInit) + Math.abs(y - yInit);
		return stats;
	}

	public Stats CalculateLengthSawHex() {
		int localSize = SIZE;
		CompactArray2d map = new CompactArray2d(localSize);

		int xInit = localSize / 2;
		int yInit = localSize / 2;
		int x = xInit;
		int y = yInit;
		map.set(x, y);

		java.util.Random r = new Random();
//		MersenneTwisterFast r = new MersenneTwisterFast(r2.nextLong());		
		int length = 0;
		int step = 0;
		int lastDir = (1+2*((x+y)%2));
		int dirMask = 15 & ~(1 << lastDir);
		int stepDir = 0;
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 4);
				switch (stepDir) {
				case 0:
					if (!map.get(x - 1, y)) {
						map.set(--x, y);
						break loop;
					}
					break;
				case 1:
					if (!map.get(x, y - 1)) {
						map.set(x, --y);
						break loop;
					}
					break;
				case 2:
					if (!map.get(x + 1, y)) {
						map.set(++x, y);
						break loop;
					}
					break;
				case 3:
					if (!map.get(x, y + 1)) {
						map.set(x, ++y);
						break loop;
					}
					break;
				}
				// only when no step was taken
				dirMask &= ~(1 << stepDir);
			}
			if (dirMask != 0) {
				lastDir = (stepDir + 2) % 4;
				dirMask = (15 & ~(1 << lastDir)) & ~(1 << (1+2*((x+y)%2)));
				step++;
				length++;
				//map.print();
			}
		}
		Stats stats = new Stats();
//		stats.pathLength = length;
		stats.stepLength = step;
//		stats.endLength = Math.sqrt((x - xInit) * (x - xInit) + (y - yInit)
//				* (y - yInit));
//		stats.manEndLength = Math.abs(x - xInit) + Math.abs(y - yInit);
		//map.print();
		return stats;
	}
	
	public Stats CalculateLengthASawTri(int[] stepSizes) {
		int localSize = SIZE;
		Array2d map = new CompactArray2d(localSize);

		int xInit = localSize / 2;
		int yInit = localSize / 2;
		int x = xInit;
		int y = yInit;
		map.set(x, y);

		java.util.Random r = new Random();
//		MersenneTwisterFast r = new MersenneTwisterFast(r2.nextLong());		
		int length = 0;
		int step = 0;
		int stepSize = stepSizes[step % stepSizes.length];
		int lastDir = r.nextInt(6);
		int dirMask = 63;
		int i = 0;
		int stepDir = 0;
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 6);
				switch (stepDir) {
					case 0:
						for (i = 0; i < stepSize && !map.get(x - i - 1, y); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(--x, y);
							}
							break loop;
						}
						break;
					case 1:
						for (i = 0; i < stepSize && !map.get(x, y - i - 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(x, --y);
							}
							break loop;
						}
						break;
					case 2:
						for (i = 0; i < stepSize && !map.get(x - i - 1, y - i - 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(--x, --y);
							}
							break loop;
						}
						break;
					case 3:
						for (i = 0; i < stepSize && !map.get(x + i + 1, y); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(++x, y);
							}
							break loop;
						}
						break;
					case 4:
						for (i = 0; i < stepSize && !map.get(x, y + i + 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(x, ++y);
							}
							break loop;
						}
						break;
					case 5:
						for (i = 0; i < stepSize && !map.get(x + i + 1, y + i + 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(++x, ++y);
							}
							break loop;
						}
						break;
				}
				// only when no step was taken
				dirMask &= ~(1 << (stepDir));
			}
			if (dirMask != 0) {
				lastDir = (stepDir + 3) % 6;
				dirMask = 63 & ~(1 << lastDir);
				step++;
				length += stepSize;
				stepSize = stepSizes[step % stepSizes.length];
			}
		}
		/**/
		Stats stats = new Stats();
		stats.pathLength = length;
		stats.stepLength = step;
		// stats.endLength = Math.sqrt((x - xInit) * (x - xInit) + (y - yInit)
		// * (y - yInit));
		// stats.manEndLength = Math.abs(x - xInit) + Math.abs(y - yInit);
		return stats;
	}
	
	public Stats CalculateLengthSawHex2() {
		int localSize = SIZE;
		Array2d map = new CompactArray2d(localSize);

		int xInit = localSize / 2;
		int yInit = localSize / 2;
		int x = xInit;
		int y = yInit;
		map.set(x, y);

		java.util.Random r = new Random();
//		MersenneTwisterFast r = new MersenneTwisterFast(r2.nextLong());		
		int length = 0;
		int step = 0;
		int lastDir = r.nextInt(6);
		int dirMask = 63;
		int i = 0;
		int stepDir = 0;
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 6);
				if (step%2==0) {
					switch (stepDir) {
						//					case 0:
						//						if(!map.get(x - 1, y)){
						//							map.set(--x, y);
						//							break loop;
						//						}
						//						break;
						//					case 1:
						//						if(!map.get(x, y-1)){
						//							map.set(x, --y);
						//							break loop;
						//						}
						//						break;
						case 2:
							if (!map.get(x - 1, y - 1)) {
								map.set(--x, --y);
								break loop;
							}
							break;
						case 3:
							if (!map.get(x + 1, y)) {
								map.set(++x, y);
								break loop;
							}
							break;
						case 4:
							if (!map.get(x, y + 1)) {
								map.set(x, ++y);
								break loop;
							}
							break;
						//					case 5:
						//						if(!map.get(x + 1, y+1)){
						//							map.set(++x, ++y);
						//							break loop;
						//						}
						//						break;
					}
				}else{
					switch (stepDir) {
						case 0:
							if (!map.get(x - 1, y)) {
								map.set(--x, y);
								break loop;
							}
							break;
						case 1:
							if (!map.get(x, y - 1)) {
								map.set(x, --y);
								break loop;
							}
							break;
//						case 2:
//							if (!map.get(x - 1, y - 1)) {
//								map.set(--x, --y);
//								break loop;
//							}
//							break;
//						case 3:
//							if (!map.get(x + 1, y)) {
//								map.set(++x, y);
//								break loop;
//							}
//							break;
//						case 4:
//							if (!map.get(x, y + 1)) {
//								map.set(x, ++y);
//								break loop;
//							}
//							break;
						case 5:
							if (!map.get(x + 1, y + 1)) {
								map.set(++x, ++y);
								break loop;
							}
							break;
					}
				}
				// only when no step was taken
				dirMask &= ~(1 << (stepDir));
			}
			if (dirMask != 0) {
				lastDir = (stepDir + 3) % 6;
				dirMask = 63 & ~(1 << lastDir);
				step++;
				length ++;
			}
		}
		/**/
		Stats stats = new Stats();
		stats.pathLength = length;
		stats.stepLength = step;
		// stats.endLength = Math.sqrt((x - xInit) * (x - xInit) + (y - yInit)
		// * (y - yInit));
		// stats.manEndLength = Math.abs(x - xInit) + Math.abs(y - yInit);
		return stats;
	}
	
	public Stats drawASaw(int[] stepSizes, WalkRenderer rend) {
		int localSize = SIZE;
		Array2d map = new CompactArray2d(localSize);

		int xInit = localSize / 2;
		int yInit = localSize / 2;
		int x = xInit;
		int y = yInit;
		map.get(x, y);
		map.set(x, y);

		java.util.Random r = new Random();
		int length = 0;
		int step = 0;
		int stepSize = stepSizes[step % stepSizes.length];
		int lastDir = r.nextInt(4);
		int dirMask = 15;
		int i = 0;
		int stepDir = 0;
		ArrayList<double[]> points = new ArrayList<double[]>();
		double[] p = {x,y};
		points.add(p);
		rend.setWalkTail(points.toArray(new double[0][0]));
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 4);
				switch (stepDir) {
				case 0:
					for (i = 0; i < stepSize && !map.get(x - i - 1, y); i++);
					if (i == stepSize) {
						for (int j = 0; j < stepSize; j++) {
							map.set(--x, y);
						}
						break loop;
					}
					break;
				case 1:
					for (i = 0; i < stepSize && !map.get(x, y - i - 1); i++);
					if (i == stepSize) {
						for (int j = 0; j < stepSize; j++) {
							map.set(x, --y);
						}
						break loop;
					}
					break;
				case 2:
					for (i = 0; i < stepSize && !map.get(x + i + 1, y); i++);
					if (i == stepSize) {
						for (int j = 0; j < stepSize; j++) {
							map.set(++x, y);
						}
						break loop;
					}
					break;
				case 3:
					for (i = 0; i < stepSize && !map.get(x, y + i + 1); i++);
					if (i == stepSize) {
						for (int j = 0; j < stepSize; j++) {
							map.set(x, ++y);
						}
						break loop;
					}
					break;
				}
				// only when no step was taken
				dirMask &= ~(1 << (stepDir));
			}
			if (dirMask != 0) {
				double[] pTemp = {x,y};
				points.add(pTemp);
				rend.setWalkTail(points.toArray(new double[0][0]));
				lastDir = (stepDir + 2) % 4;
				dirMask = 15 & ~(1 << lastDir);
				step++;
				length += stepSize;
				stepSize = stepSizes[step % stepSizes.length];
			}
		}
		/**/
		Stats stats = new Stats();
		stats.pathLength = length;
		stats.stepLength = step;
		stats.endLength = Math.sqrt((x - xInit) * (x - xInit) + (y - yInit)
				* (y - yInit));
		stats.manEndLength = Math.abs(x - xInit) + Math.abs(y - yInit);
		return stats;
	}
	
	public Stats drawASawTri(int[] stepSizes, WalkRenderer rend) {
		int localSize = SIZE;
		Array2d map = new CompactArray2d(localSize);

		int xInit = localSize / 2;
		int yInit = localSize / 2;
		int x = xInit;
		int y = yInit;
		map.set(x, y);

		java.util.Random r = new Random();
		int length = 0;
		int step = 0;
		int stepSize = stepSizes[step % stepSizes.length];
		int lastDir = r.nextInt(6);
		int dirMask = 63;
		int i = 0;
		int stepDir = 0;
		ArrayList<double[]> points = new ArrayList<double[]>();
		double[] p = {x-.5*y,y*0.866025404};
		points.add(p);
		rend.setWalkTail(points.toArray(new double[0][0]));
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 6);
				switch (stepDir) {
					case 0:
						for (i = 0; i < stepSize && !map.get(x - i - 1, y); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(--x, y);
							}
							break loop;
						}
						break;
					case 1:
						for (i = 0; i < stepSize && !map.get(x, y - i - 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(x, --y);
							}
							break loop;
						}
						break;
					case 2:
						for (i = 0; i < stepSize && !map.get(x - i - 1, y - i - 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(--x, --y);
							}
							break loop;
						}
						break;
					case 3:
						for (i = 0; i < stepSize && !map.get(x + i + 1, y); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(++x, y);
							}
							break loop;
						}
						break;
					case 4:
						for (i = 0; i < stepSize && !map.get(x, y + i + 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(x, ++y);
							}
							break loop;
						}
						break;
					case 5:
						for (i = 0; i < stepSize && !map.get(x + i + 1, y + i + 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(++x, ++y);
							}
							break loop;
						}
						break;
				}
				// only when no step was taken
				dirMask &= ~(1 << (stepDir));
			}
			if (dirMask != 0) {
				double[] pTemp = {x-0.5*y,y*0.866025404};
				points.add(pTemp);
				rend.setWalkTail(points.toArray(new double[0][0]));
				lastDir = (stepDir + 3) % 6;
				dirMask = 63 & ~(1 << lastDir);
				step++;
				length += stepSize;
				stepSize = stepSizes[step % stepSizes.length];
			}
		}
		/**/
		Stats stats = new Stats();
		stats.pathLength = length;
		stats.stepLength = step;
		// stats.endLength = Math.sqrt((x - xInit) * (x - xInit) + (y - yInit)
		// * (y - yInit));
		// stats.manEndLength = Math.abs(x - xInit) + Math.abs(y - yInit);
		return stats;
	}
	
	public Stats drawASawTriHT(int[] stepSizes, WalkRenderer rend) {
		int localSize = SIZE;
		Array2d map = new CompactArray2d(localSize);

		int xInit = localSize / 2;
		int yInit = localSize / 2;
		int x = xInit;
		int y = yInit;
		map.set(x, y);

		java.util.Random r = new Random();
		int length = 0;
		int step = 0;
		int stepSize = stepSizes[step % stepSizes.length];
		int lastDir = r.nextInt(6);
		int dirMask = 63;
		int i = 0;
		int stepDir = 0;
		ArrayList<double[]> points = new ArrayList<double[]>();
		double[] p = {x-.5*y,y*0.866025404};
		points.add(p);
		rend.setWalkTail(points.toArray(new double[0][0]));
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 6);
				switch (stepDir) {
					case 0:
						for (i = 0; i < stepSize && !map.get(x - i - 1, y); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(--x, y);
							}
							break loop;
						}
						break;
					case 1:
						for (i = 0; i < stepSize && !map.get(x, y - i - 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(x, --y);
							}
							break loop;
						}
						break;
					case 2:
						for (i = 0; i < stepSize && !map.get(x - i - 1, y - i - 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(--x, --y);
							}
							break loop;
						}
						break;
					case 3:
						for (i = 0; i < stepSize && !map.get(x + i + 1, y); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(++x, y);
							}
							break loop;
						}
						break;
					case 4:
						for (i = 0; i < stepSize && !map.get(x, y + i + 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(x, ++y);
							}
							break loop;
						}
						break;
					case 5:
						for (i = 0; i < stepSize && !map.get(x + i + 1, y + i + 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(++x, ++y);
							}
							break loop;
						}
						break;
				}
				// only when no step was taken
				dirMask &= ~(1 << (stepDir));
			}
			if (dirMask != 0) {
				double[] pTemp = {x-0.5*y,y*0.866025404};
				points.add(pTemp);
				rend.setWalkTail(points.toArray(new double[0][0]));
				lastDir = (stepDir + 3) % 6;
				dirMask = 63 & ~(1 << lastDir);
				step++;
				length += stepSize;
				stepSize = stepSizes[step % stepSizes.length];
			}
		}
		
		stepSize = stepSizes[stepSizes.length-1];
		lastDir = r.nextInt(6);
		dirMask = 63;
		ArrayList<double[]> points2 = new ArrayList<double[]>();
		double[] p2 = {x-.5*y,y*0.866025404};
		points2.add(p2);
		rend.setWalkHead(points.toArray(new double[0][0]));
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 6);
				switch (stepDir) {
					case 0:
						for (i = 0; i < stepSize && !map.get(x - i - 1, y); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(--x, y);
							}
							break loop;
						}
						break;
					case 1:
						for (i = 0; i < stepSize && !map.get(x, y - i - 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(x, --y);
							}
							break loop;
						}
						break;
					case 2:
						for (i = 0; i < stepSize && !map.get(x - i - 1, y - i - 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(--x, --y);
							}
							break loop;
						}
						break;
					case 3:
						for (i = 0; i < stepSize && !map.get(x + i + 1, y); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(++x, y);
							}
							break loop;
						}
						break;
					case 4:
						for (i = 0; i < stepSize && !map.get(x, y + i + 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(x, ++y);
							}
							break loop;
						}
						break;
					case 5:
						for (i = 0; i < stepSize && !map.get(x + i + 1, y + i + 1); i++);
						if (i == stepSize) {
							for (int j = 0; j < stepSize; j++) {
								map.set(++x, ++y);
							}
							break loop;
						}
						break;
				}
				// only when no step was taken
				dirMask &= ~(1 << (stepDir));
			}
			if (dirMask != 0) {
				double[] pTemp = {x-0.5*y,y*0.866025404};
				points2.add(pTemp);
				rend.setWalkHead(points2.toArray(new double[0][0]));
				lastDir = (stepDir + 3) % 6;
				dirMask = 63 & ~(1 << lastDir);
				step++;
				length += stepSize;
				stepSize = stepSizes[step % stepSizes.length];
			}
		}
		/**/
		Stats stats = new Stats();
		stats.pathLength = length;
		stats.stepLength = step;
		return stats;
	}
	
	public Stats drawSawHex(WalkRenderer rend) {
		int localSize = SIZE;
		CompactArray2d map = new CompactArray2d(localSize);

		int xInit = localSize / 2;
		int yInit = localSize / 2;
		int x = xInit;
		int y = yInit;
		map.set(x, y);

		java.util.Random r = new Random();
		//MersenneTwisterFast r = new MersenneTwisterFast(r2.nextLong());
		int length = 0;
		int step = 0;
		int lastDir = (1+2*((x+y)%2));
		int dirMask = 15 & ~(1 << lastDir);
		int stepDir = 0;
		ArrayDeque<double[]> points = new ArrayDeque<double[]>();
		double[] p = {x*0.866025404,1.5*y-0.5*((x+y)%2)};
		points.add(p);
		rend.setWalkTail(points.toArray(new double[0][0]));
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 4);
				switch (stepDir) {
				case 0:
					if (!map.get(x - 1, y)) {
						map.set(--x, y);
						break loop;
					}
					break;
				case 1:
					if (!map.get(x, y - 1)) {
						map.set(x, --y);
						break loop;
					}
					break;
				case 2:
					if (!map.get(x + 1, y)) {
						map.set(++x, y);
						break loop;
					}
					break;
				case 3:
					if (!map.get(x, y + 1)) {
						map.set(x, ++y);
						break loop;
					}
					break;
				}
				// only when no step was taken
				dirMask &= ~(1 << stepDir);
			}
			if (dirMask != 0) {
				double[] pTemp = {x*0.866025404,1.5*y-.5*((x+y)%2)};
				points.add(pTemp);
				rend.setWalkTail(points.toArray(new double[0][0]));
				lastDir = (stepDir + 2) % 4;
				dirMask = (15 & ~(1 << lastDir)) & ~(1 << (1+2*((x+y)%2)));
				step++;
				length++;
				//map.print();
			}
		}
		Stats stats = new Stats();
//		stats.pathLength = length;
		stats.stepLength = step;
//		stats.endLength = Math.sqrt((x - xInit) * (x - xInit) + (y - yInit)
//				* (y - yInit));
//		stats.manEndLength = Math.abs(x - xInit) + Math.abs(y - yInit);
		//map.print();
		return stats;
	}
	
	public Stats drawSawHexHT(WalkRenderer rend) {
		int localSize = SIZE;
		CompactArray2d map = new CompactArray2d(localSize);

		int xInit = localSize / 2;
		int yInit = localSize / 2;
		int x = xInit;
		int y = yInit;
		map.set(x, y);

		java.util.Random r = new Random();
		//MersenneTwisterFast r = new MersenneTwisterFast(r2.nextLong());
		int step = 0;
		int lastDir = (1+2*((x+y)%2));
		int dirMask = 15 & ~(1 << lastDir);
		int stepDir = 0;
		ArrayDeque<double[]> points = new ArrayDeque<double[]>();
		double[] p = {x*0.866025404,1.5*y-0.5*((x+y)%2)};
		points.add(p);
		rend.setWalkTail(points.toArray(new double[0][0]));
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 4);
				switch (stepDir) {
				case 0:
					if (!map.get(x - 1, y)) {
						map.set(--x, y);
						break loop;
					}
					break;
				case 1:
					if (!map.get(x, y - 1)) {
						map.set(x, --y);
						break loop;
					}
					break;
				case 2:
					if (!map.get(x + 1, y)) {
						map.set(++x, y);
						break loop;
					}
					break;
				case 3:
					if (!map.get(x, y + 1)) {
						map.set(x, ++y);
						break loop;
					}
					break;
				}
				// only when no step was taken
				dirMask &= ~(1 << stepDir);
			}
			if (dirMask != 0) {
				double[] pTemp = {x*0.866025404,1.5*y-.5*((x+y)%2)};
				points.add(pTemp);
				rend.setWalkTail(points.toArray(new double[0][0]));
				lastDir = (stepDir + 2) % 4;
				dirMask = (15 & ~(1 << lastDir)) & ~(1 << (1+2*((x+y)%2)));
				step++;
			}
		}
		x=xInit;
		y=yInit;
		lastDir = (1+2*((x+y)%2));
		dirMask = 15 & ~(1 << lastDir);
		ArrayDeque<double[]> points2 = new ArrayDeque<double[]>();
		double[] p2 = {x*0.866025404,1.5*y-0.5*((x+y)%2)};
		points2.add(p2);
		rend.setWalkHead(points2.toArray(new double[0][0]));
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 4);
				switch (stepDir) {
				case 0:
					if (!map.get(x - 1, y)) {
						map.set(--x, y);
						break loop;
					}
					break;
				case 1:
					if (!map.get(x, y - 1)) {
						map.set(x, --y);
						break loop;
					}
					break;
				case 2:
					if (!map.get(x + 1, y)) {
						map.set(++x, y);
						break loop;
					}
					break;
				case 3:
					if (!map.get(x, y + 1)) {
						map.set(x, ++y);
						break loop;
					}
					break;
				}
				// only when no step was taken
				dirMask &= ~(1 << stepDir);
			}
			if (dirMask != 0) {
				double[] pTemp = {x*0.866025404,1.5*y-.5*((x+y)%2)};
				points2.add(pTemp);
				rend.setWalkHead(points2.toArray(new double[0][0]));
				lastDir = (stepDir + 2) % 4;
				dirMask = (15 & ~(1 << lastDir)) & ~(1 << (1+2*((x+y)%2)));
				step++;
			}
		}
		Stats stats = new Stats();
		stats.stepLength = step;
		return stats;
	}
	
	public Stats drawSawHex2(WalkRenderer rend) {
		int localSize = SIZE;
		Array2d map = new CompactArray2d(localSize);

		int xInit = localSize / 2;
		int yInit = localSize / 2;
		int x = xInit;
		int y = yInit;
		map.set(x, y);

		java.util.Random r = new Random();
//		MersenneTwisterFast r = new MersenneTwisterFast(r2.nextLong());		
		int length = 0;
		int step = 0;
		int lastDir = r.nextInt(6);
		int dirMask = 63;
		int i = 0;
		int stepDir = 0;
		ArrayList<double[]> points = new ArrayList<double[]>();
		double[] p = {x-0.5*y,y*0.866025404};
		points.add(p);
		rend.setWalkTail(points.toArray(new double[0][0]));
		while (dirMask != 0) {
			loop: while (dirMask != 0) {
				stepDir = random(lastDir, dirMask, r, 6);
				if (step%2==0) {
					switch (stepDir) {
						//					case 0:
						//						if(!map.get(x - 1, y)){
						//							map.set(--x, y);
						//							break loop;
						//						}
						//						break;
						//					case 1:
						//						if(!map.get(x, y-1)){
						//							map.set(x, --y);
						//							break loop;
						//						}
						//						break;
						case 2:
							if (!map.get(x - 1, y - 1)) {
								map.set(--x, --y);
								break loop;
							}
							break;
						case 3:
							if (!map.get(x + 1, y)) {
								map.set(++x, y);
								break loop;
							}
							break;
						case 4:
							if (!map.get(x, y + 1)) {
								map.set(x, ++y);
								break loop;
							}
							break;
						//					case 5:
						//						if(!map.get(x + 1, y+1)){
						//							map.set(++x, ++y);
						//							break loop;
						//						}
						//						break;
					}
				}else{
					switch (stepDir) {
						case 0:
							if (!map.get(x - 1, y)) {
								map.set(--x, y);
								break loop;
							}
							break;
						case 1:
							if (!map.get(x, y - 1)) {
								map.set(x, --y);
								break loop;
							}
							break;
//						case 2:
//							if (!map.get(x - 1, y - 1)) {
//								map.set(--x, --y);
//								break loop;
//							}
//							break;
//						case 3:
//							if (!map.get(x + 1, y)) {
//								map.set(++x, y);
//								break loop;
//							}
//							break;
//						case 4:
//							if (!map.get(x, y + 1)) {
//								map.set(x, ++y);
//								break loop;
//							}
//							break;
						case 5:
							if (!map.get(x + 1, y + 1)) {
								map.set(++x, ++y);
								break loop;
							}
							break;
					}
				}
				// only when no step was taken
				dirMask &= ~(1 << (stepDir));
			}
			if (dirMask != 0) {
				double[] pTemp = {x-0.5*y,y*0.866025404};
				points.add(pTemp);
				rend.setWalkTail(points.toArray(new double[0][0]));
				lastDir = (stepDir + 3) % 6;
				dirMask = 63 & ~(1 << lastDir);
				step++;
				length ++;
			}
		}
		/**/
		Stats stats = new Stats();
		stats.pathLength = length;
		stats.stepLength = step;
		// stats.endLength = Math.sqrt((x - xInit) * (x - xInit) + (y - yInit)
		// * (y - yInit));
		// stats.manEndLength = Math.abs(x - xInit) + Math.abs(y - yInit);
		return stats;
	}

	private int random(int lastDir, int dirMask, Random r, int dim) {
		int rand, stepDir;
		do {
			rand = r.nextInt(dim - 1);
			stepDir = (lastDir + rand + 1) % dim;
		} while (((1 << stepDir) & dirMask) == 0);
		return stepDir;
	}
	
	private int random(int lastDir, int dirMask, MersenneTwisterFast r, int dim) {
		int rand, stepDir;
		do {
			rand = r.nextInt(dim - 1);
			stepDir = (lastDir + rand + 1) % dim;
		} while (((1 << stepDir) & dirMask) == 0);
		return stepDir;
	}

	private int calculatePossibleDirections(Array2d map, int x, int y,
			boolean[][] dir, int stepSize) {
		int directions = 0;

		dir[0] = new boolean[dir[0].length];
		dir[1] = new boolean[dir[1].length];
		dir[2] = new boolean[dir[2].length];
		dir[3] = new boolean[dir[3].length];

		boolean[] temp = dir[0];
		for (int i = 0; i < stepSize && !map.get(x - i - 1, y); i++) {
			temp[i] = true;
		}
		if (temp[stepSize - 1])
			directions++;

		temp = dir[1];
		for (int i = 0; i < stepSize && !map.get(x, y - i - 1); i++) {
			temp[i] = true;
		}
		if (temp[stepSize - 1])
			directions++;

		temp = dir[2];
		for (int i = 0; i < stepSize && !map.get(x + i + 1, y); i++) {
			temp[i] = true;
		}
		if (temp[stepSize - 1])
			directions++;

		temp = dir[3];
		for (int i = 0; i < stepSize && !map.get(x, y + i + 1); i++) {
			temp[i] = true;
		}
		if (temp[stepSize - 1])
			directions++;

		return directions;
	}
	
	
}
